{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find Leaves of Binary Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findLeaves"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #寻找二叉树的叶子节点"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一棵二叉树，请按以下要求的顺序收集它的全部节点：</p>\n",
    "\n",
    "<ol>\n",
    "\t<li>依次从左到右，每次收集并删除所有的叶子节点</li>\n",
    "\t<li>重复如上过程直到整棵树为空</li>\n",
    "</ol>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例:</strong></p>\n",
    "\n",
    "<pre><strong>输入: </strong>[1,2,3,4,5]\n",
    "&nbsp; \n",
    "&nbsp;         1\n",
    "         / \\\n",
    "        2   3\n",
    "       / \\     \n",
    "      4   5    \n",
    "\n",
    "<strong>输出: </strong>[[4,5,3],[2],[1]]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>解释:</strong></p>\n",
    "\n",
    "<p>1. 删除叶子节点&nbsp;<code>[4,5,3]</code> ，得到如下树结构：</p>\n",
    "\n",
    "<pre>          1\n",
    "         / \n",
    "        2          \n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p>2. 现在删去叶子节点&nbsp;<code>[2]</code>&nbsp;，得到如下树结构：</p>\n",
    "\n",
    "<pre>          1          \n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p>3. 现在删去叶子节点&nbsp;<code>[1]</code>&nbsp;，得到空树：</p>\n",
    "\n",
    "<pre>          []         \n",
    "</pre>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-leaves-of-binary-tree](https://leetcode.cn/problems/find-leaves-of-binary-tree/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-leaves-of-binary-tree](https://leetcode.cn/problems/find-leaves-of-binary-tree/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,4,5]', '[1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def boundaryOfBinaryTree(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        left_bound = []\n",
    "        leaves = []\n",
    "        right_bound = []\n",
    "        \n",
    "        # find left bound\n",
    "        if root.left:\n",
    "            node = root.left\n",
    "            while node.left or node.right:\n",
    "                if node.left:\n",
    "                    left_bound.append(node.val)\n",
    "                    node = node.left\n",
    "                else:\n",
    "                    left_bound.append(node.val)\n",
    "                    node = node.right\n",
    "        # find right bound\n",
    "        if root.right:\n",
    "            node = root.right\n",
    "            while node.right or node.left:\n",
    "                if node.right:\n",
    "                    right_bound.append(node.val)\n",
    "                    node = node.right\n",
    "                else:\n",
    "                    right_bound.append(node.val)\n",
    "                    node = node.left\n",
    "        # find leaves\n",
    "        def findLeaves(node):\n",
    "            nonlocal leaves\n",
    "            if not node.left and not node.right:\n",
    "                leaves.append(node.val)\n",
    "            if node.left:\n",
    "                findLeaves(node.left)\n",
    "            if node.right:\n",
    "                findLeaves(node.right)\n",
    "        if root.left or root.right:\n",
    "            findLeaves(root)\n",
    "\n",
    "        return [root.val] + left_bound + leaves + right_bound[::-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findLeaves(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return \n",
    "        \n",
    "        self.visited = set([None])\n",
    "        \n",
    "        res = []\n",
    "        \n",
    "        while root not in self.visited: \n",
    "            level = []\n",
    "            self.dfs(root, level)        \n",
    "            res.append(level)\n",
    "            \n",
    "        return res\n",
    "    \n",
    "            \n",
    "    def dfs(self, root, level):\n",
    "        if root in self.visited:\n",
    "            return \n",
    "        \n",
    "        if root.left in self.visited and root.right in self.visited:\n",
    "            level.append(root.val)\n",
    "            self.visited.add(root)\n",
    "            return \n",
    "        \n",
    "        self.dfs(root.left, level)\n",
    "        self.dfs(root.right, level)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findLeaves(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        results = []\n",
    "\n",
    "        def DFS(root):\n",
    "            if root.left is None and root.right is None:\n",
    "                if len(results) < 1:\n",
    "                    results.append([])\n",
    "                results[0].append(root.val)\n",
    "                return 1\n",
    "            \n",
    "            leftHeight = 0\n",
    "            if root.left:\n",
    "                leftHeight = DFS(root.left)\n",
    "            rightHeight = 0\n",
    "            if root.right:\n",
    "                rightHeight = DFS(root.right)\n",
    "            curHeight = max(leftHeight, rightHeight) + 1\n",
    "            if len(results) < curHeight:\n",
    "                results.append([])\n",
    "            results[curHeight - 1].append(root.val)\n",
    "            return curHeight\n",
    "        \n",
    "        _ = DFS(root)\n",
    "\n",
    "        return results"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findLeaves(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        indegrees = collections.Counter()\n",
    "        parentDict = {}\n",
    "        queue = []\n",
    "\n",
    "        def helper(node, parent):\n",
    "            if not node:\n",
    "                return\n",
    "            if not indegrees[node]:\n",
    "                indegrees[node] = 0\n",
    "            indegrees[parent] += 1\n",
    "            parentDict[node] = parent\n",
    "            helper(node.left, node)\n",
    "            helper(node.right, node)\n",
    "        \n",
    "        helper(root, None)\n",
    "        for k, v in indegrees.items():\n",
    "            if v == 0:\n",
    "                queue.append(k)\n",
    "        \n",
    "        res = []\n",
    "        while queue:\n",
    "            # print(queue)\n",
    "            nxtQueue = []\n",
    "            if queue[0] == None:\n",
    "                break\n",
    "            res.append([tn.val for tn in queue])\n",
    "            for node in queue:\n",
    "                parent = parentDict[node]\n",
    "                indegrees[parent] -= 1\n",
    "                if indegrees[parent] == 0:\n",
    "                    nxtQueue.append(parent)\n",
    "            queue = nxtQueue\n",
    "        \n",
    "        # print(res)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findLeaves(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        res = []\n",
    "        while root:\n",
    "            self.nodes = []\n",
    "            root = self.removeLeaves(root)\n",
    "            res.append(self.nodes)\n",
    "\n",
    "        return res \n",
    "\n",
    "    def removeLeaves(self, root):\n",
    "        if root is None:\n",
    "            return None \n",
    "\n",
    "        if root.left is None and root.right is None:\n",
    "            self.nodes.append(root.val)\n",
    "            return None\n",
    "\n",
    "        root.left = self.removeLeaves(root.left)\n",
    "        root.right = self.removeLeaves(root.right)\n",
    "\n",
    "        return root\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findLeaves(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "\n",
    "        res = []\n",
    "        def dfs(root):\n",
    "            nonlocal res\n",
    "            if root is None:\n",
    "                return -1\n",
    "            \n",
    "            level = max(dfs(root.left), dfs(root.right)) + 1\n",
    "            if len(res) == level:\n",
    "                res.append([])\n",
    "            res[level].append(root.val)\n",
    "            return level\n",
    "        dfs(root)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findLeaves(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        res = []\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return -1\n",
    "            left = dfs(node.left)\n",
    "            right = dfs(node.right)\n",
    "            curDepth = max(left, right) + 1\n",
    "            if curDepth >= len(res):\n",
    "                res.append([])\n",
    "            res[curDepth].append(node.val)\n",
    "            return curDepth\n",
    "        \n",
    "        dfs(root)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findLeaves(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        ans=[]\n",
    "        vis=set()\n",
    "        def dfs(r):\n",
    "            if not r:\n",
    "                return \n",
    "            if r.left:\n",
    "                if r.left.left==None and r.left.right==None:\n",
    "                    ans.append(r.left.val)\n",
    "                    r.left=None\n",
    "            if r.right:\n",
    "                if r.right.left==None and r.right.right==None:\n",
    "                    ans.append(r.right.val)\n",
    "                    r.right=None\n",
    "            \n",
    "            dfs(r.left)\n",
    "          \n",
    "            dfs(r.right)\n",
    "            return \n",
    "\n",
    "        res=[]\n",
    "        while root.left or root.right:\n",
    "            ans=[]\n",
    "            dfs(root)\n",
    "            res.append(ans)\n",
    "      \n",
    "        res.append([root.val])\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findLeaves(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        ### 这就是自下而上的统计，你要统计的就是高度\n",
    "        dic=collections.defaultdict(list)\n",
    "        def dfs(root):\n",
    "            if not root: return 0\n",
    "            l,r=dfs(root.left),dfs(root.right)\n",
    "            d=max(l,r)+1\n",
    "            dic[d].append(root.val)\n",
    "            return d\n",
    "\n",
    "        dep=dfs(root)\n",
    "        res=[dic[i] for i in range(1,dep+1)]\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findLeaves(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        def max_depth(root: Optional[TreeNode]) -> int:\n",
    "            if root is None:\n",
    "                return 0\n",
    "            left_max_depth = max_depth(root.left)\n",
    "            right_max_depth = max_depth(root.right)\n",
    "            root_max_depth = max(left_max_depth, right_max_depth) + 1\n",
    "            result[root_max_depth].append(root.val)\n",
    "            return root_max_depth\n",
    "        \n",
    "        result = collections.defaultdict(list)\n",
    "        max_depth(root)\n",
    "        return [v for v in result.values()]\n",
    "\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findLeaves(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return 0\n",
    "            l, r = dfs(root.left), dfs(root.right)\n",
    "            depth = max(r,l)+1\n",
    "            res[depth].append(root.val)\n",
    "            return depth\n",
    "        res = collections.defaultdict(list)\n",
    "        dfs(root)\n",
    "        return [v for v in res.values()]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findLeaves(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        collected = set()\n",
    "        def get_leaves(node):\n",
    "            if not node or node in collected:\n",
    "                return []\n",
    "            \n",
    "            children = get_leaves(node.left) + \\\n",
    "                get_leaves(node.right)\n",
    "        \n",
    "            if not children:\n",
    "                collected.add(node)\n",
    "                return [node]\n",
    "            else:\n",
    "                return children\n",
    "        \n",
    "        layer = get_leaves(root)\n",
    "        res = []\n",
    "        while layer:\n",
    "            res.append([i.val for i in layer])\n",
    "            layer = get_leaves(root)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findLeaves(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        lt=list()\n",
    "        st=set()\n",
    "        if root is None: return []\n",
    "        def yz(p):\n",
    "            if p is None : return \n",
    "            if (p.left is None or p.left in st ) and (p.right is None or   p.right in st):\n",
    "                lt.append(p.val)\n",
    "                st.add(p)\n",
    "            else:\n",
    "                if p.left and p.left not in st: yz(p.left)\n",
    "                if p.right and p.right not in st: yz(p.right)\n",
    "        ans=[]\n",
    "        while(1):\n",
    "            yz(root)\n",
    "            \n",
    "            # print(lt)\n",
    "            ans.append(lt[::])\n",
    "            lt=list()\n",
    "            if root in st:\n",
    "                break\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findLeaves(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        res = {}\n",
    "        def dfs(curr):\n",
    "            if not curr: return 0\n",
    "            ld = dfs(curr.left)\n",
    "            rd = dfs(curr.right)\n",
    "            curr_d = max(ld, rd)+1\n",
    "            if curr_d not in res.keys():\n",
    "                res[curr_d] = [curr.val]\n",
    "            else:\n",
    "                res[curr_d].append(curr.val)\n",
    "            return curr_d\n",
    "        \n",
    "        dfs(root)\n",
    "        ret = [v for v in res.values()]\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findLeaves(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return 0\n",
    "            l,r = dfs(root.left),dfs(root.right)\n",
    "            depth = max(l,r) + 1\n",
    "            res[depth].append(root.val)\n",
    "            return depth\n",
    "        res = collections.defaultdict(list)\n",
    "        dfs(root)\n",
    "        return [v for v in res.values()]\n",
    "        # def dfs(root):\n",
    "        #     if not root:\n",
    "        #         return 0\n",
    "        #     l,r = dfs(root.left),dfs(root.right)\n",
    "        #     depth = max(l,r) + 1\n",
    "        #     res[depth].append(root.val)\n",
    "        #     return depth\n",
    "        # res = collections.defaultdict(list)\n",
    "        # dfs(root)\n",
    "        # return [v for v in res.values()]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findLeaves(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        res=collections.defaultdict(list)\n",
    "        def helper(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "            left = helper(node.left)\n",
    "            right = helper(node.right)\n",
    "            cur = max(left,right)+1\n",
    "            res[cur].append(node.val)\n",
    "            return cur\n",
    "        helper(root)\n",
    "        return [v for v in res.values()]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findLeaves(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        res = []\n",
    "\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "            depth = max(dfs(node.left), dfs(node.right)) + 1\n",
    "            while len(res) < depth:\n",
    "                res.append([])\n",
    "            res[depth - 1].append(node.val)\n",
    "            return depth\n",
    "        \n",
    "        dfs(root)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLeaves(self, root: TreeNode) -> List[List[int]]:\n",
    "        # 自底向上递归\n",
    "        def dfs(root):\n",
    "            if not root:return 0\n",
    "            l,r=dfs(root.left),dfs(root.right)\n",
    "            depth=max(l,r)+1\n",
    "            res[depth].append(root.val)\n",
    "            return depth\n",
    "\n",
    "        res=collections.defaultdict(list)\n",
    "        dfs(root)\n",
    "        return [v for v in res.values()]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findLeaves(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        \n",
    "        def dfs(root, ans):\n",
    "            if root.left is None and root.right is None:\n",
    "                ans.append(root.val)\n",
    "                return None \n",
    "            if root.left:\n",
    "                root.left = dfs(root.left, ans) \n",
    "            if root.right:\n",
    "                root.right = dfs(root.right, ans) \n",
    "            return root \n",
    "        ans = []\n",
    "        while root.left or root.right:\n",
    "            tmp = []\n",
    "            dfs(root, tmp)\n",
    "            ans.append(tmp) \n",
    "        ans.append([root.val])\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findLeaves(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        def dfs(root):\n",
    "            if not root: return 0\n",
    "            l, r = dfs(root.left), dfs(root.right)\n",
    "            d = max(l,r)+1\n",
    "            dep_dic[d-1].append(root.val)\n",
    "            return d\n",
    "            \n",
    "        dep_dic = collections.defaultdict(list)   \n",
    "        dep = dfs(root)\n",
    "        \n",
    "        return [dep_dic[i] for i in range(dep)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findLeaves(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        layers = collections.defaultdict(list)\n",
    "\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "\n",
    "            layer_left = dfs(node.left)\n",
    "            layer_right = dfs(node.right)\n",
    "            layer = max(layer_left, layer_right)\n",
    "            layers[layer].append(node.val)\n",
    "            return layer + 1\n",
    "\n",
    "        dfs(root)\n",
    "\n",
    "        ret = []\n",
    "        i = 0\n",
    "        while i in layers:\n",
    "            ret.append(layers[i])\n",
    "            i += 1\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findLeaves(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        ans = collections.defaultdict(list)\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return 0\n",
    "            l, r = dfs(root.left), dfs(root.right)\n",
    "            cur = max(l, r) + 1\n",
    "            ans[cur].append(root.val)\n",
    "            return cur\n",
    "        dfs(root)\n",
    "        \n",
    "        return [v for v in ans.values()]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findLeaves(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        res = []\n",
    "        self.backorder(root, res)\n",
    "        return res\n",
    "\n",
    "    def backorder(self, node: Optional[TreeNode], res: List[List[int]]) -> int:\n",
    "        if node is None:    return -1\n",
    "\n",
    "        left = self.backorder(node.left, res)\n",
    "        right = self.backorder(node.right, res)\n",
    "        cur = max(left, right) + 1\n",
    "        if len(res) == cur:\n",
    "            res.append([])\n",
    "        res[cur].append(node.val)\n",
    "\n",
    "        return cur\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findLeaves(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        def dele(root: Optional[TreeNode]) -> bool:\n",
    "            if not root: return False\n",
    "            if not root.left and not root.right:\n",
    "                res[-1].append(root.val)\n",
    "                return True\n",
    "            l,r = dele(root.left),dele(root.right)\n",
    "            if l: root.left = None\n",
    "            if r: root.right = None\n",
    "            return False\n",
    "        res = []\n",
    "        flag = False\n",
    "        while not flag:\n",
    "            res.append([])\n",
    "            flag = dele(root)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findLeaves(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        ans = collections.defaultdict(list)\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return 0\n",
    "            l, r = dfs(root.left), dfs(root.right)\n",
    "            cur = max(l, r) + 1\n",
    "            ans[cur].append(root.val)\n",
    "            return cur\n",
    "        dfs(root)\n",
    "        print(ans)\n",
    "        return [v for v in ans.values()]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findLeaves(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return 0\n",
    "            l, r = dfs(root.left), dfs(root.right)\n",
    "            depth = max(l, r) + 1\n",
    "            res[depth].append(root.val)\n",
    "            return depth\n",
    "\n",
    "        res = defaultdict(list)\n",
    "        dfs(root)\n",
    "        return [v for v in res.values()]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findLeaves(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        parents = {}\n",
    "        children_count = collections.defaultdict(int)\n",
    "\n",
    "        leaves = []\n",
    "\n",
    "        def dfs(node, parent):\n",
    "            if not node:\n",
    "                return\n",
    "            parents[node] = parent\n",
    "            children_count[parent] += 1\n",
    "\n",
    "            if not node.left and not node.right:\n",
    "                leaves.append(node)\n",
    "\n",
    "            dfs(node.left, node)\n",
    "            dfs(node.right, node)\n",
    "\n",
    "        dfs(root, None)\n",
    "\n",
    "        ret = []\n",
    "        while leaves:\n",
    "            ret.append([l.val for l in leaves])\n",
    "            new_leaves = []\n",
    "            for leaf in leaves:\n",
    "                parent = parents[leaf]\n",
    "                if not parent:\n",
    "                    break\n",
    "                children_count[parent] -= 1\n",
    "                if children_count[parent] == 0:\n",
    "                    new_leaves.append(parent)\n",
    "            leaves = new_leaves\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findLeaves(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        self.res = []\n",
    "        self.maxdepth(root)\n",
    "        return self.res\n",
    "\n",
    "    def maxdepth(self, root):\n",
    "        if not root:\n",
    "            return 0\n",
    "        h = max(self.maxdepth(root.left), self.maxdepth(root.right)) + 1\n",
    "        if len(self.res) < h:\n",
    "            self.res.append([])\n",
    "        self.res[h-1].append(root.val)\n",
    "        return h"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findLeaves(self, root: TreeNode) -> List[List[int]]:\n",
    "        # 自底向上递归\n",
    "        def dfs(root):\n",
    "            if not root:return 0\n",
    "            l,r=dfs(root.left),dfs(root.right)\n",
    "            depth=max(l,r)+1\n",
    "            res[depth].append(root.val)\n",
    "            return depth\n",
    "\n",
    "        res=collections.defaultdict(list)\n",
    "        dfs(root)\n",
    "        return [v for v in res.values()]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findLeaves(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "\n",
    "        def dfs(root):\n",
    "            nonlocal res\n",
    "            if not root:\n",
    "                return 0\n",
    "            l,r = dfs(root.left),dfs(root.right)\n",
    "            depth = max(l,r)+1\n",
    "            res[depth].append(root.val)\n",
    "            return depth\n",
    "        \n",
    "        res = collections.defaultdict(list)\n",
    "        dfs(root)\n",
    "        return [v for v in res.values()]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findLeaves(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        def dfs(root):\n",
    "            if not root: return 0\n",
    "            l, r = dfs(root.left), dfs(root.right)\n",
    "            depth = max(l, r) + 1\n",
    "            res[depth].append(root.val)\n",
    "            return depth \n",
    "        \n",
    "        res = collections.defaultdict(list)\n",
    "        dfs(root)\n",
    "        return [v for v in res.values()]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findLeaves(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        def dfs(root):\n",
    "            if not root: return 0\n",
    "            l, r = dfs(root.left), dfs(root.right)\n",
    "            depth = max(l, r) + 1\n",
    "            res[depth].append(root.val)\n",
    "            return depth\n",
    "\n",
    "        res = collections.defaultdict(list)\n",
    "        dfs(root)\n",
    "        return [v for v in res.values()]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findLeaves(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        levelNode = collections.defaultdict(list)\n",
    "        def helper(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "            left = helper(node.left)\n",
    "            right = helper(node.right)\n",
    "            cur = max(left, right) + 1\n",
    "            levelNode[cur].append(node.val) \n",
    "            return cur   \n",
    "\n",
    "        helper(root)\n",
    "        res = []\n",
    "        for k,v in levelNode.items():\n",
    "            res.append(v)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\"\"\"\n",
    "最外层的深度是0，一层层的深度往里面递增\n",
    "碰到4，就是0\n",
    "碰到2，左右来改变都是0，就是max(left, right) + 1\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def findLeaves(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        def dfs(root, res):\n",
    "            if not root:\n",
    "                return -1\n",
    "            \n",
    "            left = dfs(root.left, res)\n",
    "            right = dfs(root.right, res)\n",
    "            depth = max(left, right) + 1\n",
    "\n",
    "            if depth + 1 > len(res):\n",
    "                res.append([])\n",
    "\n",
    "            res[depth].append(root.val)\n",
    "            return depth\n",
    "\n",
    "        res = []\n",
    "        dfs(root, res)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findLeaves(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        self.res = []\n",
    "        self.getHeights(root)\n",
    "        return self.res\n",
    "\n",
    "    def getHeights(self, node:TreeNode)->int:\n",
    "        if node is None:\n",
    "            return -1\n",
    "        left = self.getHeights(node.left)\n",
    "        right = self.getHeights(node.right)\n",
    "        cur = 1+max(left, right)\n",
    "        if len(self.res)==cur:\n",
    "            self.res.append([])\n",
    "        self.res[cur].append(node.val)\n",
    "        return cur\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findLeaves(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        def bfs(node):\n",
    "            if not node.left and not node.right:\n",
    "                return [node.val], True\n",
    "            ret = []\n",
    "            if node.left:\n",
    "                left, isLeaf =  bfs(node.left)\n",
    "                if isLeaf:\n",
    "                    node.left = None\n",
    "                ret = ret + left\n",
    "            if node.right:\n",
    "                right, isLeaf = bfs(node.right)\n",
    "                if isLeaf:\n",
    "                    node.right = None\n",
    "                ret = ret + right\n",
    "            return ret, False\n",
    "        ans = []\n",
    "        dummyHead = TreeNode()\n",
    "        dummyHead.left = root\n",
    "        while dummyHead.left:\n",
    "            ans.append(bfs(dummyHead)[0])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findLeaves(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        self.res = []\n",
    "\n",
    "        self.maxDepth(root)\n",
    "\n",
    "        return self.res\n",
    "\n",
    "    def maxDepth(self, root):\n",
    "        if root is None:\n",
    "            return 0\n",
    "\n",
    "        left_depth = self.maxDepth(root.left)\n",
    "        right_depth = self.maxDepth(root.right)\n",
    "\n",
    "        child_depth = max(left_depth, right_depth)\n",
    "        if child_depth >= len(self.res):\n",
    "            self.res.append([root.val])\n",
    "        else:\n",
    "            self.res[child_depth].append(root.val)\n",
    "\n",
    "        return child_depth + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findLeaves(self, root: TreeNode) -> List[List[int]]:\n",
    "        dic = collections.defaultdict(list)\n",
    "        \n",
    "        def dfs(root):\n",
    "            if not root: return 0\n",
    "            l, r = dfs(root.left), dfs(root.right)\n",
    "            d = max(l, r) + 1\n",
    "            dic[d-1].append(root.val)\n",
    "            return d\n",
    "        \n",
    "        dep = dfs(root)\n",
    "        res = [dic[i] for i in range(dep)]\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findLeaves(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        ans = []\n",
    "        def assignLeaves(root):\n",
    "            max_dp = 0\n",
    "            if not root:\n",
    "                return -1\n",
    "            if root.left:\n",
    "                max_dp = max(max_dp, assignLeaves(root.left)+1)\n",
    "            if root.right:\n",
    "                max_dp = max(max_dp, assignLeaves(root.right)+1)\n",
    "            if len(ans) <= max_dp:\n",
    "                ans.append([])\n",
    "            ans[max_dp].append(root.val)\n",
    "            return max_dp\n",
    "        \n",
    "        assignLeaves(root)\n",
    "        return ans\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findLeaves(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        list = []\n",
    "        level_n = self.dfs(root, list)\n",
    "        return list\n",
    "    \n",
    "    def dfs(self, root, list):\n",
    "        if root is None:\n",
    "            return -1\n",
    "        \n",
    "        level_l = self.dfs(root.left, list)\n",
    "        level_r = self.dfs(root.right, list)\n",
    "\n",
    "        level_n = max(level_l, level_r) + 1\n",
    "\n",
    "        if len(list) < level_n + 1:\n",
    "            list.append([])\n",
    "            list[level_n].append(root.val)\n",
    "        else:\n",
    "            list[level_n].append(root.val)\n",
    "\n",
    "        return level_n\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def findLeaves(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        \n",
    "        node_parent = {}\n",
    "        q = deque([])\n",
    "        def dfs(node):\n",
    "            if not node.left and not node.right:\n",
    "                q.append(node)\n",
    "                return \n",
    "            if node.left:\n",
    "                node_parent[node.left] = [node, 0]\n",
    "                dfs(node.left)\n",
    "            if node.right:\n",
    "                node_parent[node.right] = [node, 1]\n",
    "                dfs(node.right)\n",
    "        dfs(root)\n",
    "\n",
    "        res = []\n",
    "        while q:\n",
    "            sub = []\n",
    "            for _ in range(len(q)):\n",
    "                node = q.popleft()\n",
    "                sub.append(node.val)\n",
    "                if node not in node_parent:\n",
    "                    continue\n",
    "                parent, idx = node_parent[node]\n",
    "                if idx == 0:\n",
    "                    parent.left = None\n",
    "                else:\n",
    "                    parent.right = None\n",
    "                if not parent.left and not parent.right:\n",
    "                    q.append(parent)\n",
    "            res.append(list(sub))\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\"\"\"\n",
    "core: 核心思路是得到每个节点的最大深度，例如实例1, 节点4和5和3最大深度都是1，因此将他们放在同一层。1的最大深度是3，因此将它放在一层。如此，遍历每个节点。\n",
    "该题利用最大深度（参看543二叉树的直径）来解决。其本质是后序遍历。因为我们在前中序的位置先得到当前节点的最大深度。然后在后续位置，利用这个信息来更新res的结果，即将属于同一高度的叶子节点放到结果中\n",
    "\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    res = []\n",
    "    def max_depth(self, root):\n",
    "        if not root:\n",
    "            # 对于为空的节点，返回高度0\n",
    "            return 0\n",
    "        # j2：得到当前节点的所在高度\n",
    "        h = max(self.max_depth(root.left), self.max_depth(root.right)) + 1\n",
    "        # j3: 在后序位置将同一高度的节点放到res中, 首先要判断高度为h的存贮列表是否已经新建\n",
    "        if len(self.res) < h:\n",
    "            self.res.append([])\n",
    "        self.res[h-1].append(root.val)\n",
    "        return h\n",
    "    def findLeaves(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        self.res = []\n",
    "        self.max_depth(root)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findLeaves(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        cur_res = []\n",
    "        def helper(node):\n",
    "            nonlocal cur_res\n",
    "            # current node is a leaf node\n",
    "            if not node.left and not node.right:\n",
    "                cur_res.append(node.val)\n",
    "                return True\n",
    "            if node.left:\n",
    "                val = helper(node.left)\n",
    "                if val:\n",
    "                    node.left = None\n",
    "            if node.right:\n",
    "                val = helper(node.right)\n",
    "                if val:\n",
    "                    node.right = None\n",
    "            return False\n",
    "        \n",
    "        ans = []\n",
    "        root_is_leaf = False\n",
    "        while not root_is_leaf:\n",
    "            cur_res = []\n",
    "            root_is_leaf = helper(root)\n",
    "            ans.append(cur_res.copy())\n",
    "            \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findLeaves(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        node_height = defaultdict(list)\n",
    "        def dfs(node):\n",
    "            # 自底向上递归\n",
    "            if node is None:\n",
    "                return 0\n",
    "            lh, rh = dfs(node.left), dfs(node.right)\n",
    "            height = max(lh, rh) + 1\n",
    "            node_height[height].append(node.val)\n",
    "            return height\n",
    "        dfs(root)\n",
    "        res = []\n",
    "        for k,v in sorted(node_height.items(), key=lambda x:x[0]):\n",
    "            res.append(v)\n",
    "        return res\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findLeaves(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        # 自底向上递归\n",
    "        def dfs(root):\n",
    "            if not root:return 0\n",
    "            l,r=dfs(root.left),dfs(root.right)\n",
    "            depth=max(l,r)+1\n",
    "            res[depth].append(root.val)\n",
    "            return depth\n",
    "\n",
    "        res=collections.defaultdict(list)\n",
    "        dfs(root)\n",
    "        return [v for v in res.values()]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findLeaves(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        mapper = collections.defaultdict(list)\n",
    "\n",
    "\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "            left = dfs(node.left)\n",
    "            right = dfs(node.right)\n",
    "\n",
    "            high= max(left, right) + 1\n",
    "\n",
    "            mapper[high-1].append(node.val)\n",
    "            return high\n",
    "\n",
    "        total = dfs(root)\n",
    "\n",
    "        return [mapper[i] for i in range(total)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findLeaves(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        self.results, self.result = [], []\n",
    "\n",
    "        def traverse(root):\n",
    "            if not root: return None\n",
    "            if not root.left and not root.right:\n",
    "                self.result.append(root.val)\n",
    "                return None\n",
    "            left = traverse(root.left)\n",
    "            right = traverse(root.right)\n",
    "            root.left = left\n",
    "            root.right = right\n",
    "            return root\n",
    "\n",
    "        while root:\n",
    "            self.result = []\n",
    "            root = traverse(root)\n",
    "            self.results.append(self.result[:])\n",
    "        return self.results\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findLeaves(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        res = []\n",
    "        def dfs(n):\n",
    "            if n.left == None and n.right == None:\n",
    "                cur.append(n.val)\n",
    "                return True\n",
    "\n",
    "            if n.left and dfs(n.left):\n",
    "                n.left = None\n",
    "            if n.right and dfs(n.right):\n",
    "                n.right = None\n",
    "            return False\n",
    "\n",
    "        while root and (root.left or root.right):\n",
    "            cur = []\n",
    "            dfs(root)\n",
    "            res.append(cur[:])\n",
    "\n",
    "        if root:\n",
    "            res.append([root.val])\n",
    "        return res\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findLeaves(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        d = defaultdict(list)\n",
    "\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return -1\n",
    "            idx = max(dfs(root.left),dfs(root.right)) + 1\n",
    "            d[idx].append(root.val)\n",
    "            return idx\n",
    "        \n",
    "        dfs(root)\n",
    "        return list(d.values())\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findLeaves(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        g=collections.defaultdict(list)\n",
    "        in_degree={}\n",
    "        nodes = []\n",
    "        def dfs(node: TreeNode, pa: TreeNode):\n",
    "            if not node: return\n",
    "            if pa:\n",
    "                in_degree[pa] = in_degree.get(pa,0)+1\n",
    "                g[node].append(pa)\n",
    "            nodes.append(node)\n",
    "            dfs(node.left, node)\n",
    "            dfs(node.right, node)\n",
    "        dfs(root,None)\n",
    "        queue=deque([node for node in nodes if in_degree.get(node,0)==0])\n",
    "        res=[]\n",
    "        while queue:\n",
    "            level=[]\n",
    "            for i in range(len(queue)):\n",
    "                node=queue.popleft()\n",
    "                level.append(node.val)\n",
    "                for up_node in g[node]:\n",
    "                    in_degree[up_node]-=1\n",
    "                    if in_degree[up_node]==0:\n",
    "                        queue.append(up_node)\n",
    "            res.append(level)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\"\"\"\n",
    "core: 核心思路是得到每个节点的最大深度，例如实例1, 节点4和5和3最大深度都是1，因此将他们放在同一层。1的最大深度是3，因此将它放在一层。如此，遍历每个节点。\n",
    "该题利用最大深度（参看543二叉树的直径）来解决。其本质是后序遍历。因为我们在前中序的位置先得到当前节点的最大深度。然后在后续位置，利用这个信息来更新res的结果，即将属于同一高度的叶子节点放到结果中\n",
    "\n",
    "思考：从上到下来看，比如层序遍历的话，3和2是同一层的。\n",
    "但是如果，从下往上看，3和节点4,5一样都是叶子节点，他们是同一层的。\n",
    "题目的要求与相关概念的定义决定了我们看待问题的角度，从而挖掘出深层次的一些性质，然后利用这些性质和已有的一些模板套路来解决个性化的题目。\n",
    "\"\"\"\n",
    "class Solution:\n",
    "   \n",
    "    def max_depth(self, root, res):\n",
    "        if not root:\n",
    "            # 对于为空的节点，返回高度0\n",
    "            return 0\n",
    "        # j2：得到当前节点的所在高度\n",
    "        h = max(self.max_depth(root.left, res), self.max_depth(root.right, res)) + 1\n",
    "        # j3: 在后序位置将同一高度的节点放到res中, 首先要判断高度为h的存贮列表是否已经新建\n",
    "        if len(res) < h:\n",
    "            res.append([])\n",
    "        res[h-1].append(root.val)\n",
    "        return h\n",
    "    def findLeaves(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        res = []\n",
    "        self.max_depth(root, res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findLeaves(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root: return []\n",
    "        if not root.left and not root.right: return [[root.val]]\n",
    "        res = defaultdict(list)\n",
    "        def dfs(root):\n",
    "            if not root: return 0\n",
    "            l, r = dfs(root.left), dfs(root.right)\n",
    "            d = max(l, r) + 1\n",
    "            res[d].append(root.val)\n",
    "            return d \n",
    "        dfs(root)\n",
    "        return [v for v in res.values()]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findLeaves(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        res={}\n",
    "        def traverse(root):\n",
    "            if not root:\n",
    "                return 0\n",
    "            left_depth = traverse(root.left)+1\n",
    "            right_depth = traverse(root.right)+1\n",
    "\n",
    "            cur_depth = max(left_depth,right_depth)\n",
    "\n",
    "            if cur_depth not in res.keys():\n",
    "                res[cur_depth]=[]\n",
    "            \n",
    "            res[cur_depth].append(root.val)\n",
    "\n",
    "            return cur_depth\n",
    "        \n",
    "        traverse(root)\n",
    "\n",
    "        return [val for key,val in res.items()]\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findLeaves(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        self.res = []\n",
    "        self.getHeights(root)\n",
    "        return self.res\n",
    "\n",
    "    def getHeights(self, node:TreeNode)->int:\n",
    "        if node is None:\n",
    "            return -1\n",
    "        left = self.getHeights(node.left)\n",
    "        right = self.getHeights(node.right)\n",
    "        cur = 1+max(left, right)\n",
    "        if len(self.res)==cur:\n",
    "            self.res.append([])\n",
    "        self.res[cur].append(node.val)\n",
    "        return cur\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findLeaves(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        depthMap = defaultdict(list)\n",
    "\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return 0\n",
    "            l, r = dfs(root.left), dfs(root.right)\n",
    "            depthMap[max(l, r)].append(root.val)\n",
    "            return max(l, r) + 1\n",
    "\n",
    "        dfs(root)\n",
    "        return list(depthMap.values())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findLeaves(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        \n",
    "        # def dfs(node):\n",
    "        #     #nonlocal map_\n",
    "        #     if not node:\n",
    "        #         return 0\n",
    "            \n",
    "        #     left = dfs(node.left)\n",
    "        #     right = dfs(node.right)\n",
    "        #     h = max(left, right) + 1\n",
    "        #     map_[h].append(node.val)\n",
    "        #     return h\n",
    "        def dfs(node):\n",
    "            nonlocal leaves\n",
    "            if node.left:\n",
    "                if node.left.left is None and node.left.right is None:\n",
    "                    leaves.append(node.left.val)\n",
    "                    node.left = None\n",
    "            \n",
    "            if node.right:\n",
    "                if node.right.left is None and node.right.right is None:\n",
    "                    leaves.append(node.right.val)\n",
    "                    node.right = None\n",
    "            \n",
    "            if node.left:\n",
    "                dfs(node.left)\n",
    "            if node.right:\n",
    "                dfs(node.right)\n",
    "\n",
    "\n",
    "        \n",
    "        if not root:\n",
    "            return []\n",
    "        \n",
    "        # map_ = collections.defaultdict(list)\n",
    "        #_ = dfs(root)\n",
    "        anw = []\n",
    "        # for key in map_.keys():\n",
    "        #     anw.append(map_[key])\n",
    "        while root.left or root.right:\n",
    "            leaves = []\n",
    "            dfs(root)\n",
    "            anw.append(leaves)\n",
    "            print(root)\n",
    "        \n",
    "        anw.append([root.val])\n",
    "        return anw"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
